#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5; 
long long n,m,a[N],sum,p[N][15],lst,qwq;
struct node{
	int a[16],add[4];
}tree[N*4+5];
void pushup(int id)
{
	int now=0;
	for(int i=0;i<=3;++i)
		if(tree[id].add[i])
			now+=(1<<i);
	for(int j=0;j<=15;++j)
		tree[id].a[j]=0;
	for(int j=0;j<=15;++j)
		tree[id].a[j|now]+=tree[id*2].a[j]+tree[id*2+1].a[j];
}
void xg(int l,int r,int nl,int nr,int id,int z,int bj)
{
	if(nl>nr) return;
	if(nl<=l&&r<=nr)
	{
		if(bj==1)
			--tree[id].add[z];
		else
			++tree[id].add[z];
		if(l==r)
		{
			int now=0;
			for(int i=0;i<=15;++i)
				tree[id].a[i]=0;
			for(int i=0;i<=3;++i)
				if(tree[id].add[i])
					now+=(1<<i);
			tree[id].a[now]=1;
			return;
		}
		pushup(id);
		return;
	}
	int mid=(l+r)/2;
	if(mid>=nl) xg(l,mid,nl,nr,id*2,z,bj);
	if(mid<nr) xg(mid+1,r,nl,nr,id*2+1,z,bj);
	pushup(id);
}
int cz(int l,int r,int nl,int nr,int id,int x)
{
	if(nl<=l&&r<=nr)
		return tree[id].a[x];
	int mid=(l+r)/2,ans=0,now=0;
	for(int i=0;i<=3;++i)
		if(tree[id].add[i])
			now+=(1<<i);
	now=(1<<m)-1-now;
	if(mid>=nl) ans+=cz(l,mid,nl,nr,id*2,x&now);
	if(mid<nr) ans+=cz(mid+1,r,nl,nr,id*2+1,x&now);
	return ans;
}
void build(int l,int r,int id)
{
	if(l==r)
	{
		tree[id].a[0]=1;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,id*2);
	build(mid+1,r,id*2+1);
	pushup(id);
}
int main()
{
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	build(1,n,1);
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		p[a[i]][0]=i;
		for(int j=m+2;j>=1;--j)
			p[a[i]][j]=p[a[i]][j-1];
		for(int j=1;j<=m;++j)
			xg(1,n,p[a[i]][j+1]+1,p[a[i]][j],1,j-1,0);
		for(int j=1;j<=m;++j)
			xg(1,n,p[a[i]][j+2]+1,p[a[i]][j+1],1,j-1,1);
		sum+=cz(1,n,1,i,1,(1<<m)-1);
	}
	cout<<sum;
	return 0;
 } 
